package code;

public class Code21 {
	
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    	ListNode head=null;
    	ListNode p,q,pre = null;
    	p=l1;
    	q=l2;
    	while(p!=null && q!=null){
    		if(p.val<q.val){
    			if(head==null){
    				head=p;
    				pre=p;
    			}
    			else{
    				pre.next=p;
    				pre=p;
    			}
    			p=p.next;
    		}
    		else{
    			if(head==null){
    				head=q;
    				pre=q;
    			}
    			else{
    				pre.next=q;
    				pre=q;
    			}
    			q=q.next;
    		}
    	}
    	if(p!=null){
    		while(p!=null){
	    		if(head==null){
	    			head=p;
	    			pre=p;
	    		}
	    		else{
	    			pre.next=p;
	    			pre=p;
	    		}
	    		p=p.next;
    		}
    	}
    	if(q!=null){
    		while(q!=null){
    			if(head==null){
    				head=q;
    				pre=q;
    			}
    			else{
    				pre.next=q;
    				pre=q;
    			}
    			q=q.next;
    		}
    	}
        return head;
    }
}
